/*
题目：验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

    节点的左子树只包含 小于 当前节点的数。
    节点的右子树只包含 大于 当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。
https://leetcode.cn/problems/validate-binary-search-tree/
 */

public class IsValidBST {
    public boolean isValidBST(TreeNode root) {
        //必须满足：leftChild < root,  rightChild > root
        return checkBST(root, Long.MAX_VALUE, Long.MIN_VALUE);
    }

    private boolean checkBST(TreeNode root, long upper, long lower) {
        if (root == null) return true;
        if (root.val >= upper || root.val <= lower) return false;
        //             左孩子可以无穷小，但是不能大于root，           右孩子可以无穷大，但是不能小于root
        return checkBST(root.left, root.val, lower) && checkBST(root.right, upper, root.val);
    }
}
